/*-----------------
**-----------------
** Auther: coanor
** Date:2009.10.11
*/

#include <stdlib.h>
#include <stdio.h>

#define ARR_SZ 16

int main()
{
  int count[ARR_SZ] = {0};
  int count_2[ARR_SZ] = {0};
  int temp[ARR_SZ] = {0};
  int R[ARR_SZ] = {503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703};
  int i,j;
  
  /* Origin algorithm C */
  for (i = ARR_SZ - 1; i>0; --i) 
  {
    for (j = i-1; j >=0; --j) 
    {
      if (R[i] == R[j]) 
      {
        if (j < i) 
        {
          if (count[i] > count[j]) 
          {
	          count[j]++;
            printf("count_j++.\n");				       
          } 
          else if (count[i] < count[j]) 
          {
	          count[i]++;
	          printf("count_i++.\n");				        
          } 
          else 
          {
            /* now, j < i,R[j]'s position is before R[i]'s,
            ** we plan to make it a stable sort, so count[i] 
            ** increase by 1.
            */
            count[i]++;
            printf("Origin: R_j equals to R_i.\n");
          }
	      }
        continue; 
      }
      if (R[i] > R[j])
         count[i]++;
      else
         count[j]++;
    }
  }

  printf("\n");
  
  for (i = 0; i < ARR_SZ; ++i) 
  { 
    temp[count[i]] = R[i];
  }

  /* print origin order */
  for (i = 0; i < ARR_SZ; ++i) 
  {
    printf ("%5d", R[i]);
  }
  
  printf("\n");
  
  /* print last order, depend on COUNT[N] */
  for (i = 0; i < ARR_SZ; ++i) 
  {
    printf ("%5d", temp[i]);
  }     
  
  exit(0);
}
